In the latter half of the twentieth century, there began a phenomenon known as the information revolution. While the information revolution is a historical development broader in scope than any one event or machine, no single device has come to represent the information revolution more than the digital electronic computer. The development of computer systems has surely been a revolution. Each year, computer systems grow faster, store more data, and provide more applications to their users.
A modern computer system typically comprises hardware in the form of one or more central processing units (CPU) for processing instructions, memory for storing instructions and other data, and other supporting hardware necessary to transfer information, communicate with the external world, and so forth. From the standpoint of the computer's hardware, most systems operate in fundamentally the same manner. Processors are capable of performing a limited set of very simple operations, such as arithmetic, logical comparisons, and movement of data from one location to another. But each operation is performed very quickly. Programs which direct a computer to perform massive numbers of these simple operations give the illusion that the computer is doing something sophisticated. What is perceived by the user as a new or improved capability of a computer system is made possible by performing essentially the same set of very simple operations, but doing it much faster. Therefore continuing improvements to computer systems require that these systems be made ever faster.
The overall speed at which a computer system performs day-to-day tasks (also called “throughput”) can be increased by making various improvements to the computer's hardware design, which in one way or another increase the average number of simple operations performed per unit of time. The overall speed of the system can also be increased by making algorithmic improvements to the system design, and particularly, to the design of software executing on the system. Unlike most hardware improvements, many algorithmic improvements to software increase the throughput not by increasing the average number of operations executed per unit time, but by reducing the total number of operations which must be executed to perform a given task.
Complex systems may be used to support a variety of applications, but one common use is the maintenance of large databases, from which information may be obtained. Large databases usually support some form of database query for obtaining information which is extracted from selected database fields and records. Such queries can consume significant system resources, particularly processor resources, and the speed at which queries are performed can have a substantial influence on the overall system throughput.
Conceptually, a database may be viewed as one or more tables of information, each table having a large number of entries (analogous to row of a table), each entry having multiple respective data fields (analogous to columns of the table). The function of a database query is to find all rows, for which the data in the columns of the row matches some set of parameters defined by the query. A query may be as simple as matching a single column field to a specified value, but is often far more complex, involving multiple field values and logical conditions.
To support queries, a database typically includes one or more indexes for some of the database fields. An index is a sorting of the records in one of the database tables according to the value of a corresponding field. For example, if the database table contains records about people, one of the fields may contain a birthdate, and a corresponding index contains a sorting of the records by birthdate. If a query requests the records of all persons born before a particular date, the sorted index is used to find the responsive records, without the need to examine each and every record to determine whether there is a match. A well-designed database typically contains a respective index for each field having an ordered value which is likely to be used in queries.
Execution of a query involves retrieving and examining records in the database according to some search strategy. For any given logical query, not all search strategies are equal. Various factors may affect the choice of optimum search strategy. In particular, where a logical AND (or logical OR) of multiple conditions is specified, the sequential order in which the conditions are evaluated and the use of indexes can make a significant difference in the time required to execute the query.
If one of the conditions in a query having multiple conditions involves an indexed value, it is often, although not necessarily always, advantageous to use the index to identify a subset of records to be examined, and to examine only those records. As a simple example, suppose a query contains two conditions, A and B, conjoined by a logical AND, in which condition A involves comparing an indexed value to a constant. By accessing the index, it is possible to determine a subset of records which satisfy condition A, without the need to retrieve and examine all the records. This subset is typically obtained from a portion of the index as a form of sorted list. It is then possible to retrieve and examine each record on the sorted list to determine whether the record satisfies condition B. This type of execution strategy is referred to herein as an “index search”.
In the above example, it would alternatively be possible to retrieve each and every record in the database table, to determine whether it satisfies one of the conditions (e.g., condition A), and if so, to determine whether it also satisfies the other condition. This type of execution strategy is referred to herein as a “table scan”.
In general, the total number of records retrieved and examined will be fewer in the case of an index search, so it may appear that such a search would always be faster, or at least as fast. However, this is not always the case. When performing an index search, records are accessed in the indexed order, which is unrelated to the way in which the records are stored on a storage device, such as a rotating magnetic disk drive. Thus, from the standpoint of storage location, the order of record access is more or less random. On the other hand, when performing a table scan, records are retrieved in an order related to the way in which they are stored, to optimize storage accesses. E.g., records will typically be retrieved in sequentially addressed blocks of storage. If a single block (the smallest unit of I/O) contains multiple records, all records are retrieved at the same time and examined sequentially. Sequential blocks of storage are quickly accessed from a conventional disk drive data storage device, because there is generally little or no latency and seek time. Moreover, because sequential access is predictable, it is possible to access blocks from storage in advance of CPU need. As a result of these factors, the average amount of system resource required to retrieve and examine each record is significantly less in the case of a table scan than it is in the case of an index search.
In many cases, such as that of the simple example above, whether an index search is more efficient than a table scan will depend on the number of records eliminated from consideration by the index. In the simplified example above, if condition A is false for 99% of the records, then an index search will require that only 1% of the records be retrieved and examined for satisfaction of condition B. In this case, the index search is probably faster, notwithstanding the fact that the random nature of the access requires more resource per record examined. But if condition A is false for only 10% of the records, then a table search is probably faster, because the efficiencies of sequential access will outweigh the fact that slightly more records have to be examined.
To support database queries, large databases typically include a query engine which executes the queries according to some automatically selected search strategy, using the known characteristics of the database and other factors. Some large database applications further have query optimizers which construct search strategies, and save the query and its corresponding search strategy for reuse. These strategies include, among other things, whether an index search or a table scan will be conducted.
A re-usable query may include one or more imported variable values in its logical conditions. I.e., where the query compares a field of each database record to some value, the query may be written so that the compared-to value is a variable, to be provided (“imported”) when the query is invoked for execution. In this manner, the same query can be re-used for multiple possible compared-to values, without the necessity of writing and maintaining separate queries for all possible compared-to values.
As explained above, whether an index search or a table scan is optimum for a given query depends largely on the relative number of records examined. A query optimizer or similar function may generate and save a search strategy for a query based on certain assumptions about the number of records eliminated from consideration by the indexed value. Since the number of records eliminated by the indexed value will depend on the value of the variable to which it is compared, this number could vary considerably for different executions of the same query if the query contains imported variables. A query strategy which is optimized using one variable value will not necessarily be optimal using a different query strategy. This problem can be particularly acute if a search strategy optimized for a particular variable value uses an index search, and, as a result of a change in the variable value, relatively few records are eliminated from consideration, resulting in an index search which evaluates almost the entire database table.
It would be possible to simply re-optimize a query every time it is executed, but this involves considerable overhead. If intelligent determinations could be made to automatically re-evaluate the execution strategies of queries under certain conditions, particularly where the relative number of records eliminated by an indexed value changes, the execution performance of such queries could be improved. A need therefore exists, not necessarily recognized, for an improved database query engine or optimizer which can automatically make intelligent choices in determining when to re-evaluate the execution strategies of certain queries.